/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-09-20
 * Time: 19:54
 */
public class Solution {
    private static final int MOD = 1000000007;

    public int numWays(int startPos, int endPos, int k) {
        int diff = endPos - startPos;
        int r = (diff + k) / 2;

        if (r < 0 || r > k || (diff + k) % 2 != 0) {
            return 0;
        }

        return combination(k, r);
    }

    // 计算组合数 C(n, k)
    private int combination(int n, int k) {
        if (k > n - k) {
            k = n - k;
        }

        long result = 1;
        for (int i = 0; i < k; i++) {
            result = (result * (n - i)) % MOD;
            result = (result * modInverse(i + 1, MOD)) % MOD; // 乘法逆元
        }

        return (int) result;
    }


    private long modInverse(long a, long m) {
        m = mod(m);
        long m0 = m, t, q;
        long x0 = 0, x1 = 1;

        if (m == 1) return 0;

        while (a > 1) {
            q = a / m;
            t = m;
            m = a % m;
            a = t;
            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }

        if (x1 < 0) x1 += m0;
        return x1;
    }

    private long mod(long x) {
        return (x % MOD + MOD) % MOD;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numWays(1, 2, 3)); // 输出 3
    }
}
